#include <bits/stdc++.h>
using namespace std;
const int maxn = 8+2;
bool G[maxn][maxn], vis[maxn];
int cnt[maxn], N, id[256], alph[maxn];

string ans; int best;
void dfs(string s, int wid){
    if(s.size() == N){
        if(wid<best || (wid==best && s<ans)){
            ans = s;
            best = wid;
        }
        return;
    }

    for (int u = 0; u < N; ++u) {
        if(vis[u]) continue;

        int t = 0;
        for(int v=0; v<N; ++v) if(G[u][v] && !vis[v]) ++t;
        if(t > best) continue;

        t = wid;
        for (int ch:s) {
            int v = id[ch];
            if(G[u][v])
                t = max(t, (int)(s.size() - s.find(ch)));
        }
        if(t > best) continue;

        vis[u] = true;
        string su; su.push_back(alph[u]);
       dfs(s+su, t);
        vis[u] = false;

    }
}

int ID(char ch){
    if(id[ch]<0){
        alph[N] = ch;
        id[ch] = N++;
    }
    return id[ch];
}

void init(){
    memset(id, -1, sizeof(id));
    memset(alph, -1, sizeof(alph));
    memset(cnt, 0, sizeof(cnt));
    memset(vis, false, sizeof(vis));
    memset(G, false, sizeof(G));
    N = 0;
    ans = ""; best = INT_MAX;
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    string in;
    while(cin >> in && in[0]!='#'){
        init();
        int p = 0;
        for (p = 0; p < in.size(); ++p) {
            char u = in[p];
            int i1 = ID(in[p]);

            p += 2;
            while(isalpha(in[p])){
                char v = in[p];
                int i2 = ID(in[p]);
                G[i1][i2] = true; G[i2][i1] = true;
                ++p;
            }
        }
        for (int u = 0; u < N; ++u) {
            for (int v = 0; v < N; ++v) {
                if(G[u][v]) ++cnt[u];
            }
        }
        dfs("", -1);
        for (int i = 0; i < ans.size(); ++i) {
            if(i) cout << ' ';
            cout << ans[i];
        }
        cout << " -> " << best << "\n";
    }
    return 0;
}